package day1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ch2 {


    //283
    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[index]=nums[i];
                index++;
            }
        }
        for(int i=index;i<nums.length;i++){
            nums[i]=0;
        }
    }

    //11
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;

        int max =0;

        while (left<right){
            int h = Math.max(height[left],height[right]);
            max = Math.max(max,h*(right-left));
            if(height[left]>height[right]){
                right--;
            }else {
                left ++;
            }
        }
        return max;
    }

    //15
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);

        for(int i=0;i<nums.length-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            int num = -nums[i];

            List<Integer> l = new ArrayList<>();
            l.add(nums[i]);
            l.add(Integer.MIN_VALUE);
            l.add(Integer.MIN_VALUE);

            while (left<right){
                if((nums[left]+nums[right])==num){
                    if(l.get(1)==nums[left]&&l.get(2)==nums[right]){
                        left++;
                        right--;
                    }else {
                        l.remove(1);
                        l.remove(2);
                        l.add(nums[left]);
                        l.add(nums[right]);
                        list.add(new ArrayList<>(l));
                    }
                } else if ((nums[left]+nums[right])>num) {
                    right--;
                }else {
                    left++;
                }
            }
        }
        return list;
    }

    //42
    public int trap(int[] height) {
        int len = height.length;
        int[] left = new int[len+1]; // 0->1
        int[] right = new int[len+1];

        for(int i=1;i<len+1;i++){
            left[i] = Math.max(left[i-1],height[i-1]);
        }

        for(int j=len-1;j>=0;j--){
            right[j] = Math.max(right[j+1],height[j]);
        }

        int sum=0;
        for(int k=0;k<len;k++){
            int min = Math.min(left[k+1],right[k]);
            if(min>height[k]){
                sum += min-height[k];
            }
        }


        return sum;
    }


    public static void main(String[] args) {

    }
}
